package everydayone.findDuplicate;

/**
 * @Date 2020/05/26
 * @author 王光浩
 * @Thinking 使用快慢指针（把数组当链表）
 * 		 把 i -> nums[i] 的位置
 * 		｛1,3,5,2,5,4｝ 可以看成一个 1 -> 3 -> 2 -> 5 - > 4 -> 5（然后 5 指向 4），所以这样的数组一定会形成一个环
 * 		 如果我们找到了环的入口，这个 入口的 下标就是 重复的值
 */
public class MyMethodOne {
	public int findDuplicate(int[] nums) {
		if (nums == null || nums.length ==0)
			throw new RuntimeException("数组不能为 null 或者 长度为0");
		int slow = nums[0];
		int fast = nums[nums[0]];
		//找到快慢指针相交的地方
		while (slow != fast ) {
			slow = nums[slow];		 //慢指针前进一步
			fast = nums[nums[fast]]; //快指针前进两步
		}
		//找到环的入口
		slow = 0;
		while (slow != fast ) {
			slow = nums[slow];
			fast = nums[fast];
		}
		return slow;
	}
}
